package com.mj.listen2._05_回溯;

public class Queens {

    // cols[row] = col 表示第row行第col列摆放了皇后。cols[4] = 5：第4行第5列有皇后
    // 数组索引 index 表示行号，数组的值表示列号
    int[] cols;
    // 一共有多少种合理的摆法
    int ways = 0;

    public static void main(String[] args) {
        new Queens().placeQueens(4);
    }

    /**
     * n皇后, 摆放所有皇后
     */
    private void placeQueens(int n) {
        if (n < 1) return;
        cols = new int[n];
        place(0);// 从第0行开始摆放皇后
        System.out.println(n + "皇后一共有" + ways + "种摆法");
    }

    /**
     * 从第 row 行开始摆放皇后
     */
    void place(int row) {
        // 如果已经放到了第 n 行,说明找到了一种 n 皇后的解法
        if (row == cols.length) {
            ways++;
            show();
            return;
        }

        for (int col = 0; col < cols.length; col++) { // 遍历每一列
            if (isValid(row, col)) {
                // 将row行col列摆放上皇后
                cols[row] = col;
                // 再去下一行校验摆放皇后
                place(row + 1);
            }
        }
    }

    /**
     * 判断第row行第col列是否可以摆放皇后
     */
    private boolean isValid(int row, int col) {
        // 第col行第row列已经摆放了皇后
        for (int i = 0; i < row; i++) {// 小于row，是要看当前行的前面某一列或者某一对角线上是否摆放了皇后
            // 第col行第row列已经摆放了皇后
            if (cols[i] == col) return false;
            // 第i行的皇后根第row行第col列格子处在同一斜线上
            // 45度角斜线: y-y0 = (x-x0), 则 (y-y0)/(x-x0) = 1, 表示为45度角的斜线
            if (Math.abs(col - cols[i]) == row - i) return false;
        }
        return true;
    }

    void show() {
        for (int row = 0; row < cols.length; row++) {
            for (int col = 0; col < cols.length; col++) {
                if (cols[row] == col) { // 摆放了皇后
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("--------------------------");
    }

}
